use std::{cell::RefCell, rc::Rc};
pub struct VanEmdeBoas {
    u: u32,
    min: RefCell<Option<u32>>,
    max: RefCell<Option<u32>>,
    summary: Option<Rc<VanEmdeBoas>>,
    cluster: Option<Vec<Rc<VanEmdeBoas>>>,
}

impl VanEmdeBoas {
    pub fn build(u: u32) -> Self {
        let mut v = VanEmdeBoas {
            u: u,
            min: RefCell::new(None),
            max: RefCell::new(None),
            summary: None,
            cluster: None,
        };
        if u == 2 {
            v
        } else {
            v.summary = Some(Rc::new(VanEmdeBoas::build(v.up_pow())));
            let cluster = vec![Rc::new(VanEmdeBoas::build(v.down_pow())); v.up_pow() as usize];
            v.cluster = Some(cluster);
            v
        }
    }
    pub fn up_pow(&self) -> u32 {
        2_u32.pow((((self.u as f32).log2()) / 2.0).floor() as u32)
    }
    pub fn down_pow(&self) -> u32 {
        2_u32.pow((((self.u as f32).log2()) / 2.0).ceil() as u32)
    }
    pub fn high(&self, x: u32) -> usize {
        (x / self.down_pow()) as usize
    }
    pub fn low(&self, x: u32) -> u32 {
        x % self.down_pow()
    }
    pub fn index(&self, x: u32, y: u32) -> u32 {
        x * (self.down_pow() as u32) + y
    }
    pub fn veb_tree_minimum(&self) -> Option<u32> {
        unsafe { *(self.min.as_ptr()) }
    }
    pub fn veb_tree_maximum(&self) -> Option<u32> {
        unsafe { *(self.max.as_ptr()) }
    }
    pub fn set_min(&self, v: Option<u32>) {
        *(self.min.borrow_mut()) = v;
    }
    pub fn set_max(&self, v: Option<u32>) {
        *(self.max.borrow_mut()) = v;
    }
    pub fn veb_tree_member(&self, x: u32) -> bool {
        let min = self.veb_tree_minimum();
        let max = self.veb_tree_maximum();
        if (min.is_some() && x == min.unwrap()) || (max.is_some() && x == max.unwrap()) {
            true
        } else if self.u == 2 {
            false
        } else {
            if self.cluster.is_some() {
                self.cluster.as_ref().unwrap()[self.high(x)].veb_tree_member(self.low(x))
            } else {
                false
            }
        }
    }
    pub fn veb_tree_successor(&self, x: u32) -> Option<u32> {
        if self.u == 2 {
            if x == 0 && self.veb_tree_maximum().is_some() && self.veb_tree_maximum().unwrap() == 1
            {
                Some(1)
            } else {
                None
            }
        } else if self.veb_tree_minimum().is_some() && x < self.veb_tree_minimum().unwrap() {
            self.veb_tree_minimum()
        } else {
            if self.cluster.is_some() {
                let self_cluster = self.cluster.as_ref().unwrap();
                let self_high_x = self.high(x);
                let self_low_x = self.low(x);
                let max_low = self_cluster[self_high_x].veb_tree_maximum();
                if max_low.is_some() && self_low_x < max_low.unwrap() {
                    let offset = self_cluster[self_high_x].veb_tree_successor(self_low_x);
                    if offset.is_some() {
                        Some(self.index(self_high_x as u32, offset.unwrap()))
                    } else {
                        None
                    }
                } else {
                    if self.summary.is_some() {
                        let succ_sluster = self
                            .summary
                            .as_ref()
                            .unwrap()
                            .veb_tree_successor(self_high_x as u32);
                        if succ_sluster.is_none() {
                            None
                        } else {
                            let offset =
                                self_cluster[succ_sluster.unwrap() as usize].veb_tree_minimum();
                            if offset.is_some() {
                                Some(self.index(succ_sluster.unwrap(), offset.unwrap()))
                            } else {
                                None
                            }
                        }
                    } else {
                        None
                    }
                }
            } else {
                None
            }
        }
    }
    pub fn veb_tree_predecessor(&self, x: u32) -> Option<u32> {
        if self.u == 2 {
            if x == 1 && self.veb_tree_minimum().is_some() && self.veb_tree_minimum().unwrap() == 0
            {
                Some(0)
            } else {
                None
            }
        } else if self.veb_tree_maximum().is_some() && x > self.veb_tree_maximum().unwrap() {
            self.veb_tree_maximum()
        } else {
            if self.cluster.is_some() {
                let self_cluster = self.cluster.as_ref().unwrap();
                let high_x = self.high(x);
                let low_x = self.low(x);
                let min_low = self_cluster[high_x].veb_tree_minimum();
                if min_low.is_some() && low_x > min_low.unwrap() {
                    let offset = self_cluster[high_x].veb_tree_predecessor(low_x);
                    if offset.is_some() {
                        Some(self.index(high_x as u32, offset.unwrap()))
                    } else {
                        None
                    }
                } else {
                    if self.summary.is_some() {
                        let pred_cluster = self
                            .summary
                            .as_ref()
                            .unwrap()
                            .veb_tree_predecessor(high_x as u32);
                        if pred_cluster.is_none() {
                            if self.veb_tree_minimum().is_some()
                                && x > self.veb_tree_minimum().unwrap()
                            {
                                self.veb_tree_minimum()
                            } else {
                                None
                            }
                        } else {
                            let offset =
                                self_cluster[pred_cluster.unwrap() as usize].veb_tree_maximum();
                            if offset.is_some() {
                                Some(self.index(pred_cluster.unwrap(), offset.unwrap()))
                            } else {
                                None
                            }
                        }
                    } else {
                        None
                    }
                }
            } else {
                None
            }
        }
    }
    pub fn veb_empty_tree_insert(&self, x: u32) {
        self.set_min(Some(x));
        self.set_max(Some(x));
    }
    pub fn veb_tree_insert(&self, x: u32) {
        if self.veb_tree_minimum().is_none() {
            self.veb_empty_tree_insert(x);
        } else {
            if x < self.veb_tree_minimum().unwrap() {
                self.veb_tree_insert(self.veb_tree_minimum().unwrap());
                self.set_min(Some(x));
            }
            if self.u > 2 {
                let self_cluster = self.cluster.as_ref().unwrap();
                let self_high = self.high(x);
                let self_low = self.low(x);
                if self_cluster[self_high].veb_tree_minimum().is_none() {
                    self.summary
                        .as_ref()
                        .unwrap()
                        .veb_tree_insert(self_high as u32);
                    self_cluster[self_high].veb_empty_tree_insert(self_low);
                } else {
                    self_cluster[self_high].veb_tree_insert(self_low);
                }
            }
            if self.veb_tree_maximum().is_some() && x > self.veb_tree_maximum().unwrap() {
                self.set_max(Some(x));
            }
        }
    }
    pub fn veb_tree_delete(&self, x: u32) {
        if self.veb_tree_minimum() == self.veb_tree_maximum() {
            self.set_max(None);
            self.set_min(None);
        } else if self.u == 2 {
            if x == 0 {
                self.set_min(Some(1));
            } else {
                self.set_min(Some(0));
                self.set_max(Some(0));
            }
        } else if self.veb_tree_minimum().is_some() && x == self.veb_tree_minimum().unwrap() {
            let self_summary = self.summary.as_ref().unwrap();
            let first_cluster = self_summary.veb_tree_minimum();
            if first_cluster.is_some() {
                let first = first_cluster.unwrap();
                let self_cluster = self.cluster.as_ref().unwrap();
                let y = self_cluster[first as usize].veb_tree_minimum();
                if y.is_some() {
                    let x = self.index(first, y.unwrap());
                    self.set_min(Some(x));
                    let high_x = self.high(x);
                    let low_x = self.low(x);
                    self_cluster[high_x].veb_tree_delete(low_x);
                    if self_cluster[high_x].veb_tree_minimum().is_none() {
                        self_summary.veb_tree_delete(high_x as u32);
                        if self.veb_tree_maximum().is_some()
                            && x == self.veb_tree_maximum().unwrap()
                        {
                            let summary_max = self_summary.veb_tree_maximum();
                            if summary_max.is_none() {
                                self.set_max(Some(x));
                            } else {
                                let summary_max_unwarp = summary_max.unwrap();
                                let y =
                                    self_cluster[summary_max_unwarp as usize].veb_tree_maximum();
                                if y.is_some() {
                                    self.set_max(Some(self.index(summary_max_unwarp, y.unwrap())));
                                }
                            }
                        }
                    } else if self.veb_tree_maximum().is_some()
                        && x == self.veb_tree_maximum().unwrap()
                    {
                        let y = self_cluster[high_x].veb_tree_maximum();
                        if y.is_some() {
                            self.set_max(Some(self.index(high_x as u32, y.unwrap())));
                        }
                    }
                }
            }
        }
    }
}
